package 链表相交;

class Solution {

    // 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null


    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 首先要确定是否存在交叉点 -> 如果存在交叉点，那么两个链表的末尾节点一定是相同的
        ListNode pA = headA;
        int countA = 1;
        ListNode pB = headB;
        int countB = 1;
        if( pA == null || pB == null )
            return null;
        // 找到两个链表的末尾节点
        while ( pA.next != null ){
            pA = pA.next;
            countA++;
        }
        while ( pB.next != null ){
            pB = pB.next;
            countB++;
        }
        if ( pA != pB ){
            // 不存在交叉点
            return null;
        }
        // 相交点在 | countA - countB | 处
        int num = countA - countB;
        // 长链表先走 num 个节点
        pA = headA;
        pB = headB;
        if( num > 0 ){
            for (int i = 0; i < num; i++)
                pA = pA.next;
        }else{
            for (int i = 0; i < -num; i++)
                pB = pB.next;
        }
        // 当pA 和 pB第一次相等的时候 就是我们寻找的相交点
        while ( pA != pB ){
            pA = pA.next;
            pB = pB.next;
        }
        return pA;
    }
}